From:"Anders Tiberg"<anders.tiberg@telia.com>
To:<filearchive@ticalc.org>
Subject:Nine stamps problem for the Post Office
Date:jan.8,2003


 
 I got this trial and error problem from a friend who says he first saw it in the Sunday Obser-
ver sometime in the 1960's. It was described as a nine stamps problem for the Post Office - be-
fore decimalisation. The idea is that to save money the Post Office is to issue a denomination
of nine and only nine stamps wich are to cover every cost from one to as far above a hundred as
possible, with a maximum of three stamps a letter. Only positive integers are allowed.
The best series I have achieved so far is: 1,3,4,13,22,31,33,36,37 wich covers every value from
1 onto 111:

1=1,2=1+1,3=3,4=4,5=4+1,6=4+1+1,7=4+3,8=4+4,9=4+4+1,10=4+3+3,11=4+4+3,12=4+4+4,13=13,14=13+1,
15=13+1+1,16=13+3,17=13+4,18=13+4+1,19=13+3+3,20=13+4+3,21=13+4+4,22=22,23=22+1,24=22+1+1,
25=22+3,26=22+4,27=22+4+1,28=22+3+3,29=22+4+3,30=22+4+4,31=31,32=31+1,33=33,34=33+1,35=31+4,
36=36,37=37,38=37+1,39=36+3,40=36+4,41=37+4,42=36+3+3,43=36+4+3,44=36+4+4,45=37+4+4,46=33+13,
47=33+13+1,48=31+13+4,49=33+13+3,50=33+13+4,51=37+13+1,52=36+13+3,53=36+13+4,54=37+13+4,
55=33+22,56=33+22+1,57=31+22+4,58=33+22+3,59=33+22+4,60=37+22+1,61=36+22+3,62=36+22+4,63=37+22+4,
64=33+31,65=33+31+1,66=31+31+4,67=33+31+3,68=36+31+1,69=36+33,70=37+33,71=37+33+1,72=36+36,
73=37+36,74=37+37,75=37+37+1,76=37+36+3,77=37+37+3,78=37+37+4,79=33+33+13,80=36+31+13,
81=37+31+13,82=36+33+13,83=37+33+13,84=31+31+22,85=36+36+13,86=37+36+13,87=37+37+13,88=33+33+22,
89=36+31+22,90=37+31+22,91=36+33+22,92=37+33+22,93=31+31+31,94=36+36+22,95=37+36+22,96=37+37+22,
97=33+33+31,98=36+31+31,99=33+33+33,100=36+33+31,101=37+33+31,102=36+33+33,103=37+33+33,
104=37+36+31,105=37+37+31,106=37+36+33,107=37+37+33,108=36+36+36,109=37+36+36,110=37+37+36 and
finally 111=37+37+37.


 To help me with that I've made two small programs, STAMPS1 and STAMPS2:


 STAMPS1
:ClrHome
:Prompt U
:0->H                           -> means the STO-button
:{1,3,4,13,22,31,33}->L1
:For(I,42,U)
:{0}->L2
:L2->L3
:For(J,1,dim(L1))
:I-L1(J)->A
:If A=0
:Then
:I->H
:U->J
:End
:If A>33
:A->L2((L2(1)>0)+dim(L2)
:For(K,J,dim(L1))
:A-L1(K)->B
:If B=0
:Then
:I->H
:U->J
:U->K
:End
:If B>33 and B<41
:B->L3((L3(1)>0)+dim(L3)
:For(L,K,dim(L1))
:If B=L1(L)
:Then
:I->H
:U->J
:U->K
:U->L
:End
:End
:End
:End
:If I>H
:Then
:Disp "-",I
:Pause L2
:Pause L3
:Else
:Disp I
:End
:End


 STAMPS1 gives the missing second(L2) and third(L3) stamps of a certain size from the first
list(L1) of stamps i.e numbers when there is no combination of the numbers in L1 that matches
a certain number. The numbers in L1 were taken from my friends best series: 1,3,4,13,22,31,33,
34,39 wich goes onto 107. I wanted to see if there was two numbers between 33 and 41 other than
34 and 39 that could improve the result. It's important to remember that the numbers in L2 can
be split into two, for example 72=36+36, 73=36+37 since they are the missing second stamps: for
I=76 neither 36 or 37 are in L3 but both 72 and 73 are in L2. You must also keep track of when
the number(I) divides even in two or three, for example 74=2*37, 108=3*36 and other combinations
of numbers that previously has ocurred in L2 and L3: 109=36+36+37. So you'd better make notes of
the numbers in the lists if you want to try another series. There are two more series that my
friend gave me: 1,3,4,13,21,28,35,47,58=100 and 1,3,4,13,21,27,36,52,71=102 that you could try
to improve on.	 


 STAMPS2
:ClrHome
:Prompt U
:0->H
:{1,3,4,13,22,31,33,36,37}->L1
:For(I,46,U)
:0->J
:Repeat I<=L1(J)+2max(L1              <= means smaller than or equal to
:J+1->J
:End
:For(J,J,dim(L1))
:I-L1(J)
:If Ans=0
:Then
:I->H
:U->J
:End
:For(K,J,dim(L1))
:If L1(K)=Ans
:Then
:I->H
:U->J
:U->K
:End
:For(L,K,dim(L1))
:If L1(K)+L1(L)=Ans
:Then
:I->H
:U->J
:U->K
:U->L
:End
:End
:End
:End
:If I=H
:Disp I
:If I=H
:End
:Disp "-",I
:L1


 STAMPS2 is used for verification when you think you've got a list of numbers that's better than
any of these. It runs faster than STAMPS1 so it might save you some time. Please let me know if
so or if you've got a better program. I don't know wether it is possible to prove wich series is
the best or not, but I'd be grateful if someone could let me in on this.







                  Questions and/or input write to: anders.tiberg@telia.com





